package problems;

import java.math.BigInteger;
import java.util.Map;

import lib.MathLib;

import com.google.common.collect.HashBiMap;

public class Euler044 extends AbstractEuler {

	@Override
	public Number calculate() {
		Map<Integer,BigInteger> pentagonalNumbers = HashBiMap.create();
		pentagonalNumbers.put(1, BigInteger.ONE); //P1 = 1
		for (int k = 2; k <= Integer.MAX_VALUE; k++) {
			if (pentagonalNumbers.get(k) == null) {
				pentagonalNumbers.put(k, MathLib.getPolygonalNumber(k, 5));
			}

			for (int j = k - 1; j >= 1; j--) {
				
				BigInteger numK = pentagonalNumbers.get(k);
				BigInteger numJ = pentagonalNumbers.get(j);
				BigInteger diff = numK.subtract(numJ);

				if (
					pentagonalNumbers.containsValue(diff)
				) {
					BigInteger sum = numK.add(numJ);
					fillToSize(sum, pentagonalNumbers);
					if (pentagonalNumbers.containsValue(sum)) {
						return diff;
					}
				}
			}
		}
		fail("could not find answer before reaching limits of Integer");
		return null;
	}
	
	private void fillToSize(BigInteger limit, Map<Integer,BigInteger> cache) {
		while(cache.get(cache.size()).compareTo(limit) < 0) {
			int next = cache.size() + 1;
			BigInteger numberToAdd = MathLib.getPolygonalNumber(next, 5);
			cache.put(next, numberToAdd);
		}
	}

	@Override
	protected Number getCorrectAnswer() {
		return BigInteger.valueOf(5482660);
	}

}
